/**
 * 
 * 求斐波那契数列的第k个值
 */


/** 时间复杂度是O(n^2) 要优化他*/
// const fibonacci = (n:number):any=>{
//     if(n<=0) return 0
//     if(n== 1) return 1
//     return fibonacci(n-2) + fibonacci(n-1)
// }


// console.log(fibonacci(4))

/**不要递归 用循环   记录中间的结果 时间复杂度O(n) */

const fibonacci = (n:number):any=>{
    if(n<=0) return 0
    if(n== 1) return 1
    let n1 = 1
    let n2 = 0
    let res = 0
    for(let i = 2;i<=n;i++){
        res = n1 + n2 
        n2 = n1
        n1 = res
    }
    return res
}

console.log(fibonacci(100))
